/*************************************************************
 * 
 * CopyRight(c)2007, http://www.moorwind.com/
 * email:ezhung@gmail.com
 * for free, but a email permission would be nice
 * 
 ************************************************************/
package kono.utils
{
	import kono.utils.D2Array
	
	//图， graph
	public class Graph
	{
		//图的边，使用二维数组实现， the edge of the graph built on 2-dimensonal array
		private var edges:D2Array;
		
		//图的标签， the label of the graph
		private var labels:Array;
		
		public function Graph(n:uint)
		{
			edges = new D2Array(n,n);
			labels = new Array(n);
			edges.fill(false);
		}
		
		//得到图的大小， write the size of the graph
		public function get size():uint
		{
			return labels.length;
		}
		
		//设定对应的顶点标签， set the label of the graph
		public function setLabel(vertex:uint, newLabel:*):void
		{
			labels[vertex] = newLabel;
		}
		
		//得到对应顶点标签， get the label from the given vertex in the graph
		public function getLabel(vertex:uint):*
		{
			return labels[vertex];
		}
		
		//测试一条边是否已经存在, check if the given edge exit
		public function isEdge(source:uint, target:uint):Boolean
		{
			return edges.getItem(source,target);
		}
		
		//增加一条边， add a new edge to the graph
		public function addEdge(source:uint, target:uint):void
		{
			edges.addItem(source,target,true);
		}
		
		//删除一条边， remove a edge from the graph
		public function removeEdge(source:uint, target:uint):void
		{
			edges.addItem(source,target,false);
		}
		
		//获取指定顶点的邻接点列表， get the array list of the neigbbors from the graph by given vertex
		public function neighbors(vertex:uint):Array
		{
			var i:uint, count:uint = 0;
			var answer:Array = new Array();
			
			for(i = 0; i < labels.length; i++)
			{
				if(edges.getItem(vertex,i))
					answer[count++] = i;
			}
			return answer;
		}
		
		//深度优先遍历， depth first processing
		public static function depthFirst(g:Graph, start:uint):void
		{
			var marked:Array = new Array(g.size);
			for(var i:uint = 0; i < marked.length; i++)
			{
				marked[i] = false;
			}
			depthFirstRecurse(g,start,marked);
		}
		
		private static function depthFirstRecurse(g:Graph, v:uint, marked:Array):void
		{
			var connections:Array = g.neighbors(v);
			var i:uint;
			marked[v] = true;
			
			trace(g.getLabel(v));
			
			for(i = 0; i< connections.length; i++)
			{
				if(!marked[connections[i]])
					depthFirstRecurse(g,connections[i],marked);
			}
		}
		
		//广优先遍历， breadth first processing
		public static function breadthFirst(g:Graph, start:uint):void
		{
			var que:ArrayedQueue;
			var i:uint;
			if(g.size == 1)
				que = new ArrayedQueue(1);
			else
				que = new ArrayedQueue(g.size - 1);
			
			var marked:Array = new Array(g.size);
			for(i = 0; i < marked.length; i++)
			{
				marked[i] = false;
			}
			marked[start] = true;
			que.enqueue(start);
			trace(g.getLabel(start));
			while(!que.isEmpty())
			{
				var connection:Array = g.neighbors(que.dequeue());
				for(i = 0; i < connection.length; i++)
				{
					if(!marked[connection[i]])
					{
						que.enqueue(connection[i]);
						marked[connection[i]] = true;
						trace(g.getLabel(connection[i]));
					}
				}
			}
		}
		
		//返回图的信息， return a string respreaenting the current graph
		public function toString():String
		{
			return "[Graph, size=" + labels.length + "]";
		}
	}
}